package com.camus.algorithm.impl;

import java.util.Arrays;

import com.camus.algorithm.SubsetAlgorithm4Int;

/**
 * 递归优化(数据有序的场景剪枝优化)算法求目标和的子集
 * 
 * @author jie.deng
 *
 */
public class SubsetAlgorithmOfSortPruningRecursion4IntEg implements SubsetAlgorithm4Int {

	@Override
	public int[] findSubsetOfTargetSum(int[] candidateArr, int target) {
		// 先排序，方便后面有针对性地剪枝
		Arrays.sort(candidateArr);
		
		// 前缀和，方便后面剪枝时求区间和
		int len = candidateArr.length;
		int[] prefixSumArr = new int[len];
		prefixSumArr[0] = candidateArr[0];
		for (int i = 1; i < len; i++) {
			prefixSumArr[i] = prefixSumArr[i - 1] + candidateArr[i];
		}
		
		// 递归
		return findSubsetOfTargetSum(candidateArr, target, 0, new boolean[len], prefixSumArr);
	}

	public int[] findSubsetOfTargetSum(int[] candidateArr, int target, int nextCandidateIdx, boolean[] flagArr, int[] prefixSumArr) {
		int len = candidateArr.length;
		// 1.递归终止条件
		if (target == 0) {
			return filterSubset(candidateArr, flagArr);
		}
		if (nextCandidateIdx >= candidateArr.length) {
			return null;
		}
		// 2.当前层逻辑：可以在[nextCandidateIdx,len)中选择一个
		for (int i = nextCandidateIdx; i < len; i++) {
			if (i > nextCandidateIdx && candidateArr[i] == candidateArr[i - 1]) {
				// 剪枝优化1
				continue;
			}
			if (failFast(candidateArr, target, i, prefixSumArr)) {
				// 剪枝优化2
				return null;
			}			
			flagArr[i] = true;
			// 3.递归调用下一层
			int[] arr = findSubsetOfTargetSum(candidateArr, target - candidateArr[i], i + 1, flagArr, prefixSumArr);
			// 4.回溯
			flagArr[i] = false;

			if (arr != null) {
				return arr;
			}
		}
		return null;
	}

	private int[] filterSubset(int[] candidateArr, boolean[] flagArr) {
		int len = candidateArr.length;

		int size = 0;
		for (int i = 0; i < len; i++) {
			if (flagArr[i]) {
				size++;
			}
		}

		int[] subsetArr = new int[size];
		for (int i = len - 1; i >= 0; i--) {
			if (flagArr[i]) {
				subsetArr[--size] = candidateArr[i];
			}
		}
		return subsetArr;
	}
	
	/**
	 * 
	 * @param candidateArr      升序数组
	 * @param target            目标和
	 * @param nextCandidateIdx  可选元素的索引的起始值
	 * @param prefixSumArr      升序数组的前缀和
	 * @return 从[nextCandidateIdx, len)选择n个数是否可以凑出target，肯定凑不出则返回true
	 */
	private boolean failFast(int[] candidateArr, int target, int nextCandidateIdx, int[] prefixSumArr) {
		int len = candidateArr.length;
		if (nextCandidateIdx >= len) {
			return true;
		}
		int min = candidateArr[nextCandidateIdx];
		int max = candidateArr[len - 1];
		int sum = prefixSumArr[len - 1] - (nextCandidateIdx == 0 ? 0 : prefixSumArr[nextCandidateIdx - 1]);
		if (min >= 0) {
			// 所有元素都是正数
			if (min > target) {
				// 且最小元素大于目标和
				return true;
			}
			if (sum < target) {
				// 且所有元素之和仍然小于目标和
				return true;
			}
		}
		if (max <= 0) {
			// 所有元素都是负数，
			if (max < target) {
				// 且最大元素小于目标和
				return true;
			}
			if (sum > target) {
				// 且所有元素和仍然大于目标和
				return true;
			}
		}
		return false;
	}	

}
